import collections


class Solution(object):
    def findMaximums(self, nums):
        n = len(nums)
        min_left = [0] * n
        min_right = [0] * n
        st = []
        ans = [0] * n
        for index, num in enumerate(nums):
            while st and num <= nums[st[-1]]:
                st.pop()
            if not st:
                min_left[index] = -1
            else:
                min_left[index] = st[-1]
            st.append(index)
        st = []
        for i in range(n - 1, -1, -1):
            while st and nums[i] <= nums[st[-1]]:
                st.pop()
            if not st:
                min_right[i] = n
            else:
                min_right[i] = st[-1]
            st.append(i)
        d = collections.defaultdict(list)
        for i in range(n):
            d[min_right[i] - min_left[i] - 1].append(nums[i])
        last = -float('inf')
        for i in range(n, 0, -1):
            if d[i]:
                d[i].sort(reverse=True)
                last = max(d[i][0], last)
            ans[i - 1] = last
        return ans


data = Solution()
nums = [1,7,4,4,2,5,1,6,3]
print(data.findMaximums(nums))
